A Database Management System (DBMS) is a software package that provides a reliable way to store data in a database and process it. One of the main requirements of a DBMS is to provide a coherent interface that allows application developers to manipulate data stored in a database. The architecture of most DBMSs follows a multilayer approach, where each layer is responsible for other phase of processing. Typical DBMS layers are depicted in FIG. 4 and comprise: 1) a client application, which issues a query to the DBMS; 2) a query parser, which parses the text representation of a query and creates an internal representation used by the DBMS; 3) a query optimizer, which tries to find an efficient way to execute the query and creates a query plan; 4) a query executor, which does the actual processing of the data; 5) a buffer manager, that loads data from the storage and buffers it in the memory for processing; and 6) storage, which handles storing data on persistent storage device such as hard disk.
For datasets that do not fit in memory, the DBMS typically buffers parts of data in memory using the buffer manager component. The buffer manager is responsible for handling requests received from the query executor and making decisions about what data should be cached in the memory. The data on disk is typically split into blocks (or “pages”), and both loading and buffering solutions are based on this granularity. Each database query needs to read a collection of blocks. Since the buffer is capable of caching only a part of the data, there is a need for a policy governing what data should be cached. In particular, when a new block is loaded into memory and the buffer is full, there needs to be a policy deciding which of the already-cached blocks should be evicted.
Hence it is desirable, for the DBMS, to increase the efficiency of the buffer manager layer which results in an overall performance improvement.
Most databases use quite sophisticated buffering mechanisms, but typically these are targeted at transaction processing (OLTP) scenarios. These buffering mechanisms are not good for large scans typically found in analytical (OLAP) scenarios and would cause a lot of unnecessary input/output (IO), translating to bad performance. A scan typically accesses a range or multiple ranges, each comprising a large number of blocks (e.g. 10-1000). Blocks are typically requested in sequential fashion, i.e. the order of requests corresponds to the logical order of blocks on the disk.
Some conventional systems use a “least recently used” (LRU) buffering strategy. This policy discards blocks that have not been used for the longest time. This policy however, does not perform well in case of large scans. To illustrate, in a system that contains a table consisting of 100 sequential blocks numbered 1-100, a buffer manager can hold 90% of the table. After a full scan of a table, the last 90% of the table (hence blocks 11-100) will be cached in memory. When another scan starts, it will ask for block 1. The LRU policy will look at which block to evict, and it will see that the least-recently-used block is block 11 and it will be evicted. When scanning block 2, block 12 will be evicted, and so on. When the scan gets to block 11, it will not be in memory, and block 22 will be evicted. The net effect will be that all blocks will be evicted only to be quickly re-loaded which is inefficient. It is desirable to be able to overcome this inefficiency of the LRU buffering.
An alternative policy used by some conventional systems is the “most recently used” (MRU) which is better in the case of a large scan than LRU. However, MRU is not feasible as a general purpose strategy in a real system, as it suffers in other cases, e.g. when queries access different tables and different subsets of columns. In many situations, MRU turns out to be worst possible solution leading to performing an I/O operation on every block request. For example, suppose a query reading table A is executed and table A is large enough to fill the whole buffer pool. Afterwards, a query reading table B is run. The MRU method first evicts the most recently used block from table A to replace it with a block belonging to table B. Since the block from table B is now the most recently used, it is evicted to load the next block from table B. The process continues until a query is finished leaving the buffer pool with one block belonging to table B and all other blocks belonging to table A. If subsequent queries happen to access table B as well, they effectively can not reuse cached blocks, because the buffer is occupied mostly with blocks from table A. It is desirable to achieve better performance than with the MRU approach.
Other systems attempt to modify the access pattern of a scan so that the buffer manager copes better with the scans. The idea is to make concurrent scan operations access the same data at the same time or at least data that has been recently accessed (and is still buffered). Circular scans used by Microsoft® SQL Server is an example of such a solution. However, circular scans require the query executor to accept data out-of-order which is some cases is impossible or has significant structural impact on DBMS. Another approach is to have an ability to throttle scans (IBM® DB2 as described in C. A. Lang, B. Bhattacharjee, T. Malkemus, S. Padmanabhan, and K. Wong, “Increasing Buffer-Locality For Multiple Relational Table Scans Through Grouping And Throttling”, IEEE International Conference on Data Engineering (ICDE), Istanbul, Turkey (2007.)). While maintaining the order of data delivery, throttling of scans provides benefits in only limited number of scenarios.
Another solution are “Cooperative Scans” (See Marcin Zukowski, Sandor Heman, Niels Nes, Peter Boncz, “Cooperative Scans: Dynamic Bandwidth Sharing in a DBMS”, International Conference on Very Large Databases 2007, Vienna, Austria (September 2007.)) It provides multiple benefits for scan oriented applications, typically allowing it to achieve performance much better than all other solutions. However, this approach requires very complex modifications to buffer manager component and it is also limited to scenarios where query executor can accept data delivered in an out-of-order fashion.
It is desirable to provide a method and system that improves buffer management efficiency, such as for easy integration with a modern DBMS and it is to this end that the disclosure is directed.